package com.linzm.leetcode.mid.tree.层次遍历;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author zimingl
 * @Date 2023/2/20 23:48
 * @Description: TODO
 */
public class MaxDepth104 {
    public static void main(String[] args) {
        MaxDepth104 maxDepth104 = new MaxDepth104();
        int num = maxDepth104.maxDepth3(TreeNode.getTree());
        System.out.println(num);
    }

    public int maxDepth2(TreeNode root) {
        if (root == null) return 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            while (len > 0) {
                TreeNode treeNode = queue.poll();
                if (treeNode.left != null) queue.offer(treeNode.left);
                if (treeNode.right != null) queue.offer(treeNode.right);
                len--;
            }
            depth++;
        }
        return depth;
    }

    /**
     * 递归法 求高度 左右中
     * 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
     * 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
     * 而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    /**
     * 递归法(求深度法)
     */
    //定义最大深度
    int maxnum = 0;

    public int maxDepth3(TreeNode root) {
//        ans(root, 0);
        ans2(root, 1);
        return maxnum;
    }

    //递归求解最大深度 中左右
    void ans(TreeNode tr, int tmp) {
        if (tr == null) return;
        tmp++;
        maxnum = Math.max(maxnum, tmp);
        ans(tr.left, tmp);
        ans(tr.right, tmp);
        tmp--;
    }

    void ans2(TreeNode tr, int tmp) {
        if (tr == null) return;
        maxnum = Math.max(maxnum, tmp);
        ans2(tr.left, tmp + 1);
        ans2(tr.right, tmp + 1);
    }

    int result;

    public int maxDepth4(TreeNode root) {
        result = 0;
        if (root == null) return result;
        getDepth(root, 1);
        return result;
    }

    private void getDepth(TreeNode root, int depth) {
        result = Math.max(depth, result);
        if (root.left == null && root.right == null) {
            return;
        }
        if (root.left != null) {
            getDepth(root.left, depth + 1);
        }
        if (root.right != null) {
            getDepth(root.right, depth + 1);
        }
    }

    private void getDepth2(TreeNode root, int depth) {
        // 中
        result = Math.max(depth, result);
        if (root.left == null && root.right == null) {
            return;
        }
        // 左
        if (root.left != null) {
            // 深度 +1
            depth++;
            getDepth(root.left, depth);
            // 回溯 深度 -1
            depth--;
        }
        // 右
        if (root.right != null) {
            // 深度 +1
            depth++;
            getDepth(root.right, depth);
            // 回溯 深度 -1
            depth--;
        }
    }
}

